﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;

using SimNations.City;

using Microsoft.Xna.Framework;


namespace SimNations.Pathfinding
{

    // This class uses the A* (pronounced A (star)) algorithm to find a path.
    // For more information, see:
    // http://www.policyalmanac.org/games/aStarTutorial.htm
    public class PathFinder
    {
        // MEMBER VARIABLES
        // ------------------------------------------------------------------------------------------------------------------------

        private const int MOVECOST_STRAIGHT = 10;
        private const int MOVECOST_DIAGONAL = 14;

        private bool m_bAllowOrthogonalOnly = false;    // Sets whether or not only orthogonal (non-diagonal) moves are allowed in generated paths.  

        private List<Square> m_ClosedList;
        private List<Square> m_OpenList;

        private CityTile[,] m_World = null;
        private int m_WorldWidth = 0;
        private int m_WorldHeight = 0;

        private Random m_Random = new Random();

        private Square m_StartSquare = null;        // Stores the square we start at
        private Square m_EndSquare = null;          // Stores the square to find a path to

        private TransitTypes m_TransitType = TransitTypes.Road;


        // CONSTRUCTORS
        // ------------------------------------------------------------------------------------------------------------------------

        public PathFinder()
        {
            m_ClosedList = new List<Square>();
            m_OpenList = new List<Square>();

        } // end PathFinder::PathFinder()



        // PRIVATE/PROTECTED METHODS
        // ------------------------------------------------------------------------------------------------------------------------

        private int GetMoveCount()
        {
            int count = 0;
            Square curSquare = m_EndSquare;


            if (m_EndSquare.ParentSquare == null)
                return -1;


            while (true)
            {
                if (curSquare.ParentSquare != null)
                {
                    count++;
                    curSquare = curSquare.ParentSquare;
                }
                else
                {
                    break;
                }

            } // end while


            return count;

        } // end PathFinder::GetMovecount();

        private int SquareListContains(List<Square> list, Vector2 pos)
        {
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i].Position == pos)
                    return i;
            }

            return -1;

        } // end PathFinder::SquareListContains(List<Square>, Vector2)


        // METHODS
        // ------------------------------------------------------------------------------------------------------------------------

        public Vector2[] FindRoute()
        {
            int index = -1;
            int moves = -1;

            List<Square> NewOpenList = null;
            
            Square currentSquare = null;
            Square testSquare = null;

            Vector2 checkPos;
            Vector2[] route;

            int lowestFScore;




            m_ClosedList.Clear();




            if (m_StartSquare == null)
            {
                throw new ENoStartPointException("The starting square has not been specified!  Cannot generate a route starting from an unknown point!");

            }
            if (m_StartSquare == null)
            {
                throw new ENoEndPointException("The ending (destination) square has not been specified!  Cannot generate a route ending at an unknown point!");

            }


            //Console.Write("Finding a path from startSquare( {0}, {1} ) to ", this.StartingSquare.Position.X, this.StartingSquare.Position.Y);
            //Console.Write("endSquare( {0}, {1} )\n", this.EndingSquare.Position.X, this.EndingSquare.Position.Y);

 
            m_OpenList.Add(m_StartSquare);

            while (true)
            {
                NewOpenList = new List<Square>();

                if (m_OpenList.Count == 0)
                    break;


                for (int i = 0; i < m_OpenList.Count; i++)
                {
                    lowestFScore = 8000000; // this is just an arbitrarily high number to ensure this variable starts out higher than any F-Scores we calculate below

                    testSquare = m_OpenList[i];


                    // Check tiles that are adjacent to the current square and add them to the
                    // open list if they are travellable.
                    for (int y = -1; y <= 1; y++)
                    {
                        for (int x = -1; x <= 1; x++)
                        {
                            // Get the position of the next square to check
                            checkPos.X = testSquare.Position.X + x;
                            checkPos.Y = testSquare.Position.Y + y;


                            // Only allow orthogonal moves if m_bAllowOrthogonalOnly is set to true.
                            if ((m_bAllowOrthogonalOnly && testSquare.IsOrthogonal(checkPos)) ||
                                 (!m_bAllowOrthogonalOnly))
                            {

                                // Check that this position is valid
                                if ((checkPos.X >= 0 && checkPos.X < m_WorldWidth) &&
                                     (checkPos.Y >= 0 && checkPos.Y < m_WorldHeight))
                                {
                                    // Check if this square is travelable.
                                    if (m_World[(int)checkPos.X, (int)checkPos.Y].TransitType == m_TransitType)
                                    {
                                        // Check that this square is not already in the closed list
                                        index = SquareListContains(m_ClosedList, checkPos);
                                        if (index >= 0)
                                        {
                                            // Since this square is already in the closed list, see if getting
                                            // here through that square is a better path than the one we already
                                            // have.
                                            if (m_ClosedList[index].IsOrthogonal(testSquare))
                                            {
                                                if (m_ClosedList[index].G_Score + MOVECOST_STRAIGHT < testSquare.G_Score)
                                                    testSquare.ParentSquare = m_ClosedList[index];
                                            }
                                            else
                                            {
                                                if (m_ClosedList[index].G_Score + MOVECOST_DIAGONAL < testSquare.G_Score)
                                                    testSquare.ParentSquare = m_ClosedList[index];
                                            }

                                        }
                                        else if (SquareListContains(NewOpenList, checkPos) == -1)    // Only add this square to the open list if it isnt already there.
                                        {
                                            currentSquare = new Square(checkPos);
                                            currentSquare.ParentSquare = testSquare;

                                            if (checkPos == m_EndSquare.Position)
                                                m_EndSquare = currentSquare;



                                            // Check if this square is vertical/horizontal from the previous square.
                                            if (testSquare.IsOrthogonal(currentSquare))
                                            {
                                                currentSquare.G_Score = testSquare.G_Score + MOVECOST_STRAIGHT;
                                            }
                                            else
                                            {
                                                // The current tile is diagonal from the previous tile.
                                                currentSquare.G_Score = testSquare.G_Score + MOVECOST_DIAGONAL;
                                            }


                                            currentSquare.H_Score = Math.Abs((int)(currentSquare.Position.X - m_EndSquare.Position.X)) +
                                                                    Math.Abs((int)(currentSquare.Position.Y - m_EndSquare.Position.Y));

                                            currentSquare.F_Score = currentSquare.G_Score + currentSquare.H_Score;


                                            // Check if this square's F score is lower than the lowest we've seen so far.
                                            if (currentSquare.F_Score < lowestFScore)
                                                lowestFScore = currentSquare.F_Score;


                                            // Add this square to the open list
                                            //Console.WriteLine("Added square( {0}, {1} ) to the open list.", currentSquare.Position.X, currentSquare.Position.Y);
                                            NewOpenList.Add(currentSquare);

                                        }
                                    }

                                }
                            }


                        } // end for x
                    } // end for y


                    //Console.WriteLine("Added square( {0}, {1} ) to the closed list.", currentSquare.Position.X, currentSquare.Position.Y);
                    m_ClosedList.Add(testSquare);

                } // end for i



                m_OpenList = NewOpenList;

            } // end while


            // Now make a Vector2 array of the appropriate size and copy the route
            // data into it.
            moves = GetMoveCount();
            
            if (moves < 0)
                throw new ENoPathFoundException("No path could be found from the starting point to the ending point!");
            
            route = new Vector2[moves];



            Vector2 vCoordinates;
            currentSquare = m_EndSquare;
            for (int i = moves - 1; i >= 0; i--)
            {
                vCoordinates = new Vector2(0, 0);

                if (currentSquare.ParentSquare != null)
                {
                    vCoordinates.X = currentSquare.Position.X;
                    vCoordinates.Y = currentSquare.Position.Y;

                    route[i] = vCoordinates;


                    currentSquare = currentSquare.ParentSquare;
                }
            } // end for i


            // Return the generated route
            return route;


        } // end PathFinder::FindRoute()


        // DEBUG METHODS
        // ------------------------------------------------------------------------------------------------------------------------

#if (DEBUG)
        // put all debug methods in here...
#endif


        // PROPERTIES
        // ------------------------------------------------------------------------------------------------------------------------

        public bool AllowOrthogonalMovesOnly
        {
            get
            {
                return m_bAllowOrthogonalOnly;
            }
            set
            {
                m_bAllowOrthogonalOnly = value;
            }
        } // end property AllowOrthogonalMovesOnly

        public Square EndingSquare
        {
            get
            {
                return m_EndSquare;
            }
            set
            {
                m_EndSquare = value;
            }
        } // end property EndingSquare

        public Square StartingSquare
        {
            get
            {
                return m_StartSquare;
            }
            set
            {
                m_StartSquare = value;
            }
        } // end property StartingSquare

        public TransitTypes TransitType
        {
            get
            {
                return m_TransitType;
            }
            set
            {
                m_TransitType = value;
            }
        } // end property TransitType

        public CityTile[,] World
        {
            get
            {
                return m_World;
            }
            set
            {
                m_World = value;
            }
        } // end property World

        public int WorldWidth
        {
            get
            {
                return m_WorldWidth;
            }
            set
            {
                m_WorldWidth = value;
            }
        } // end property WorldWidth

        public int WorldHeight
        {
            get
            {
                return m_WorldHeight;
            }
            set
            {
                m_WorldHeight = value;
            }
        } // end property WorldHeight



        // EVENTS
        // ------------------------------------------------------------------------------------------------------------------------


    } // end class PathFinder



    // OTHER STUFF
    // ------------------------------------------------------------------------------------------------------------------------

    public class ENoPathFoundException : Exception
    {
        public ENoPathFoundException(string message)
            : base(message)
        {

        } // end ENoPathFoundException::ENoPathFoundException(string)


    } // end class ENoPathFoundException


    public class ENoStartPointException : Exception
    {
        public ENoStartPointException(string message)
            : base(message)
        {

        } // end ENoStartPointException::ENoStartPointException(string)


    } // end class ENoStartPointException


    public class ENoEndPointException : Exception
    {
        public ENoEndPointException(string message)
            : base(message)
        {

        } // end ENoEndPointException::ENoEndPointException(string)


    } // end class ENoEndPointException



}
